#include "stdafx.h"
#include "MergeSort.h"
#include <iostream>

bool MergeSort(int Arr[], int start, int end)
{
    bool sorted = true;
    if(start < end) // if only one element its already sorted
    {
        int n = end - start + 1;
        int p = start;
        int q = end - (n / 2);
        int r = end;
        
        MergeSort(Arr, p, q);
        MergeSort(Arr, q+1, r);
        sorted = Merge(Arr, p, q, r);
        if(sorted == false)
            int br = 1;
    }
    return sorted;
}

bool Merge(int Arr[], int p, int q, int r)
{
    bool merged = false;

    if(p <= q && q < r)
    {
        int *Left = NULL, *Right = NULL;
        try 
        {
            int n1 = q - p + 1;
            int n2 = r - (q + 1) + 1;

            // Create Auxillary array Left and Right to store p to q and q+1 to r resp
            // This Auxillary array is created to get the result back into Arr[p..q]
            Left = new int[n1];
            Right = new int[n2];
            memcpy(Left, &Arr[p], sizeof(int) * n1);
            memcpy(Right, &Arr[q+1], sizeof(int) * n2);

            int i = 0, j = 0;
            for(int k = p; k <= r; ++k)
            {   
                if(i >= n1)                   
                    Arr[k] = Right[j++]; // Left array already merged fully, copy top element from right array for the remaining loop                                    
                else if(j >= n2)                   
                    Arr[k] = Left[i++]; // Right array already merged fully, copy top element from left array for the remaining loop                                   }
                else if(Left[i] <= Right[j])
                    Arr[k] = Left[i++];     
                else
                    Arr[k] = Right[j++];                
            }
            merged = true;
        }
        catch(std::bad_alloc)
        {
            delete Left;
            delete Right;
        }
    }    
    return merged;
}